#include <iostream>

using namespace std;

int main(int argc, char *args[])
{
	const int MAX = 50000;
	int A[MAX];
	int T;
	scanf("%d", &T);
	for (int t = 0; t < T; t++) {
		int n;
		scanf("%d", &n);
		for (int j = 0; j < n; j++) {
			scanf("%d", A + j);
		}
		//int **arr = new int*[n];
		//for (int j = 0; j < n; j++) {
		//	arr[j] = new int[n];
		//}
		//for (int j = 0; j < n ; j++) {
		//	arr[j][j] = A[j];
		//}

		//int max = -500000000;
		//for (int step = 1; step < n ; step++) {
		//	for (int j = 0; j + step < n; j += step) {
		//		int k = j + step;
		//		max = -500000000;
		//		int sum = 0;
		//		for (int l = j; l < k; l++) {
		//			sum = (arr[j][l] + arr[l + 1][k]);
		//			sum = sum > arr[j][l] ? sum : arr[j][l];
		//			sum = sum > arr[l + 1][k] ? sum : arr[l + 1][k];
		//			if (sum > max) 
		//				max = sum;
		//		}

		//		arr[j][k] = max;
		//		printf("%d %d %d\n", j, k, max);
		//	}
		//}

		//printf("%d\n", arr[0][n - 1]);
		int *forward = new int[n];
		int *backward = new int[n];
		
		int maxSum = forward[0] = A[0];
		int totalSum = A[0];
		for (int i = 1; i < n; i++) {
			/*totalSum += A[i];
			if (maxSum < totalSum) {
				maxSum = totalSum;
			}
			forward[i] = maxSum;*/
			int preTotalSum = totalSum;
			if (totalSum < 0) {
				totalSum = totalSum < A[i] ? A[i] : totalSum;
			} else {
				totalSum += A[i];
			}
			if (preTotalSum > totalSum) { // The sum goes down
				forward[i] = maxSum;
			} else {
				if (maxSum < totalSum) {
					maxSum = totalSum;
				}
				forward[i] = maxSum;
			}
			//printf("%d\n", forward[i]);
		}

		maxSum = backward[n - 1] = A[n - 1];
		totalSum = A[n - 1];
		for (int i = n - 2; i >= 0; --i) {
			//if ((totalSum + A[i]) < totalSum) { // The sum goes down
			//	backward[i] = maxSum;
			//} else {
			//	if (maxSum < (totalSum + A[i])) {
			//		maxSum = totalSum + A[i];
			//	}
			//	backward[i] = maxSum;
			//}
			//totalSum += A[i];

			int preTotalSum = totalSum;
			if (totalSum < 0) {
				totalSum = totalSum < A[i] ? A[i] : totalSum;
			} else {
				totalSum += A[i];
			}
			if (preTotalSum > totalSum) { // The sum goes down
				backward[i] = maxSum;
			} else {
				if (maxSum < totalSum) {
					maxSum = totalSum;
				}
				backward[i] = maxSum;
			}
			//printf("%d\n", backward[i]);
		}

		
		maxSum = forward[0] + backward[1];
		for (int i = 1; i < n - 1; i++) {
			if (maxSum < (forward[i] + backward[i + 1]))
				maxSum = forward[i] + backward[i + 1];
		}
		printf("%d\n", maxSum);
		//for (int j = 0; j < n; j++) {
		//	delete[] arr[j];
		//}
		//delete[] arr;

		delete[] forward;
		delete[] backward;


	}
	return 0;
}